#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
      int val;
      struct ListNode *next;
 };
 
truct ListNode* merge(struct ListNode* headA, struct ListNode* headB)
{
    if (headA == NULL || headB == NULL)
        return headA == NULL ? headB : headA;

    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = newHead;
    struct ListNode* cur1 = headA;
    struct ListNode* cur2 = headB;

    while (cur1 && cur2)
    {
        if (cur1->val < cur2->val)
        {
            cur->next = cur1;
            cur1 = cur1->next;
        }
        else
        {
            cur->next = cur2;
            cur2 = cur2->next;
        }
        cur = cur->next;
    }

    cur->next = cur1 == NULL ? cur2 : cur1;

    struct ListNode* ret = newHead->next;
    free(newHead);
    return ret;
}

struct ListNode* sortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;

    // struct ListNode* left = NULL;
    // struct ListNode* mid = head;
    // struct ListNode* right = head;
    // while (right && right->next)
    // {
    //     left = mid;
    //     mid = mid->next;
    //     right = right->next->next;
    // }

    // left->next = NULL;

    // return merge(sortList(head), sortList(mid));

    int length = 0;
    struct ListNode* cur = head;
    while (cur)
    {
        length++;
        cur = cur->next;
    }

    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newHead->next = head;
    for (int subLength = 1; subLength < length; subLength *= 2)
    {
        cur = newHead->next;
        struct ListNode* prev = newHead;
        while (cur)
        {
            struct ListNode* head1 = cur;
            for (int i = 1; i < subLength && cur->next != NULL; i++)
                cur = cur->next;

            struct ListNode* temp = cur->next;
            cur->next = NULL;
            cur = temp;

            if (cur)
            {
                struct ListNode* head2 = cur;
                for (int i = 1; i < subLength && cur->next != NULL; i++)
                    cur = cur->next;

                temp = cur->next;
                cur->next = NULL;

                struct ListNode* merged = merge(head1, head2);
                prev->next = merged;

                while (prev->next)
                    prev = prev->next;
                prev->next = temp;


                cur = temp;
            }
        }
    }

    struct ListNode* ret = newHead->next;
    free(newHead);
    return ret;
}

int main()
{
    struct ListNode* node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node1->val = 4;
    struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node2->val = 2;
    struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node3->val = 1;
    //struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    //node4->val = 3;

    node1->next = node2;
    node2->next = node3;
    node3->next = NULL;
    //node4->next = NULL;

    struct ListNode* ret = sortList(node1);

    return 0;
}